package pro1.双指针.t27;

import java.util.Arrays;

/**
 * @Author xingyu Xue
 * @Date 2024/2/4 19:50
 * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
 *
 * 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
 * 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
 *
 * 这道题，看上去很简单，但是它说了一句，不要使用额外的数组空间。
 *
 *
 * 这道题的测试用例，它会打印你返回的数字，并按照这个数组的大小（返回的数字）打印数组
 */
public class 移除元素 {
    /**
     * 双指针法：主要是用到两个指针    1·指向当前将要处理的元素， 2·指向下一个将要赋值的位置
     *
     * 时间复杂度：O(n)O(n)O(n)，其中 nnn 为序列的长度。我们只需要遍历该序列至多两次。
     *
     * 空间复杂度：O(1)O(1)O(1)。我们只需要常数的空间保存若干变量。
     *
     * @param nums
     * @param val
     * @return
     */
    public static int removeElement(int[] nums, int val) {
        int i = 0; //i是将要赋值的位置
        for (int j = 0; j < nums.length; j++) {//j ：原数组的位置
            if (nums[j] != val) {
                nums[i] = nums[j];
                i++;
            }
        }
        return i;
    }
//右指针 right 指向当前将要处理的元素，左指针left 指向下一个将要赋值的位置
    public static int removeElement2(int[] nums, int val) {
        int n = nums.length;
        int left = 0;
        for (int right = 0; right < n; right++) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left++;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3, 2, 2, 3};
        System.out.println(removeElement3(nums, 3));

        System.out.println(Arrays.toString(nums));
    }



    public static int removeElement3(int[] nums, int val) {
        int n= nums.length;
        int right =0; //右指针 是将要赋值的数组的位置
        for (int left = 0; left < n; left++) { //left是原数组

            if (nums[left]!= val){ //数组的值不等于val 说明这个值该放入新数组中
                nums[right]=nums[left];
                right++;// 赋值完一个值后，新数组的下标跟着加一。
            }

        }
        return right;
    }


}
